package com.huangyi;

import java.util.*;

public class Main {
    public static void main(String[] args) {
        //飞地的数量
        class Solution {
            boolean[][] vis;
            int m, n;
            int[] dx = {0, 0, -1, 1};
            int[] dy = {-1, 1, 0, 0};

            public int numEnclaves(int[][] grid) {
                m = grid.length;
                n = grid[0].length;
                vis = new boolean[m][n];
                Queue<int[]> q = new LinkedList<>();

                // 1) 边界多源入队并标记访问
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        boolean onEdge = (i == 0 || i == m - 1 || j == 0 || j == n - 1);
                        if (onEdge && grid[i][j] == 1 && !vis[i][j]) {
                            q.offer(new int[]{i, j});
                            vis[i][j] = true;
                        }
                    }
                }

                // 2) 多源 BFS 扩张所有能通到边界的陆地
                while (!q.isEmpty()) {
                    int[] cur = q.poll();
                    int a = cur[0], b = cur[1];
                    for (int k = 0; k < 4; k++) {
                        int x = a + dx[k], y = b + dy[k];
                        if (x >= 0 && x < m && y >= 0 && y < n
                                && !vis[x][y] && grid[x][y] == 1) {
                            q.offer(new int[]{x, y});
                            vis[x][y] = true;
                        }
                    }
                }

                // 3) 统计仍未访问的陆地
                int ret = 0;
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        if (!vis[i][j] && grid[i][j] == 1) ret++;
                    }
                }
                return ret;
            }
        }


        //地图中的最高点
        class Solution2 {
            int m, n;
            int[] dx = {0, 0, -1, 1};
            int[] dy = {-1, 1, 0, 0};

            public int[][] highestPeak(int[][] isWater) {
                m = isWater.length;
                n = isWater[0].length;
                Queue<int[]> q = new LinkedList<>();

                // 水=0 并入队；陆地=-1 代表未赋值
                for (int i = 0; i < m; i++) {
                    for (int j = 0; j < n; j++) {
                        if (isWater[i][j] == 1) {
                            isWater[i][j] = 0;
                            q.offer(new int[]{i, j});
                        } else {
                            isWater[i][j] = -1; // 未赋值
                        }
                    }
                }

                while (!q.isEmpty()) {
                    int[] cur = q.poll();
                    int a = cur[0], b = cur[1];
                    for (int k = 0; k < 4; k++) {
                        int x = a + dx[k], y = b + dy[k];
                        if (x >= 0 && x < m && y >= 0 && y < n && isWater[x][y] == -1) {
                            isWater[x][y] = isWater[a][b] + 1; // 邻居高度 = 当前 + 1
                            q.offer(new int[]{x, y});
                        }
                    }
                }
                return isWater;
            }
        }
    }
}